import math
import random
from datetime import datetime
from argparse import ArgumentParser
from common import format_timedelta


def s(a, b, p):
    # s > 0: p在ab左边
    # s = 0: p在ab上
    # s < 0: p在ab右边
    x1, y1 = a
    x2, y2 = b
    x3, y3 = p
    return (x1 - x3) * (y2 - y3) - (y1 - y3) * (x2 - x3)


def enum(q):
    def is_within_triangle(a, b, c, p):
        x = s(a, b, p)
        y = s(b, c, p)
        z = s(c, a, p)
        if (x >= 0 and y >= 0 and z >= 0) or (x <= 0 and y <= 0 and z <= 0):
            # print(a, b, c, p)
            return True
        return False        

    is_vertex = [1 for _ in range(len(q))]
    for i in range(len(q)):
        for j in range(i + 1, len(q)):
            for k in range(j + 1, len(q)):
                for l in range(len(q)):
                    if l == i or l == j or l == k:
                        continue
                    if is_within_triangle(q[i], q[j], q[k], q[l]):
                        is_vertex[l] = 0

    left_idx = 0
    right_idx = 0
    for i in range(1, len(q)):
        if is_vertex[i] == 0:
            continue
        if q[i][0] < q[left_idx][0]:
            left_idx = i
        if q[i][0] > q[right_idx][0]:
            right_idx = i

    up = []
    low = []
    for i in range(len(q)):
        if i == left_idx or i == right_idx or is_vertex[i] == 0:
            continue
        if s(q[left_idx], q[right_idx], q[i]) < 0:
            up.append(i)
        else:
            low.append(i)

    up = sorted(up, key=lambda p: q[i][0])
    low = sorted(low, key=lambda p: -q[i][0])
    return [left_idx] + up + [right_idx] + low


def cosine(p):
    return p[0] / math.sqrt(p[0] * p[0] + p[1] * p[1])


def graham_scan_inner(q, indices):
    stack = [indices[0], indices[1], indices[2]]
    for i in range(3, len(indices)):
        while s(q[stack[-2]], q[stack[-1]], q[indices[i]]) <= 0:
            stack = stack[:-1]
        stack.append(indices[i])
    return stack


def graham_scan(q):
    q0_idx = 0
    for i in range(1, len(q)):
        if q[i][1] < q[q0_idx][1]:
            q0_idx = i
    q0 = q[q0_idx]

    indices = [q0_idx] + sorted([i for i in range(len(q)) if i != q0_idx], key=lambda i: -cosine((q[i][0] - q0[0], q[i][1] - q0[1])))
    stack = graham_scan_inner(q, indices)
    return stack


def divide_and_conquer(q):
    def divide_and_conquer_inner(q, indices):
        def merge(q, indices_retain, indices_split1, indices_split2):
            # 判断归并是否结束
            def is_finish(arrays, indices):
                finish_count = 0
                for i in range(len(arrays)):
                    if indices[i] >= len(arrays[i]):
                        finish_count += 1
                return finish_count >= len(arrays)

            origin = q[indices_retain[0]]
            result = [indices_retain[0]]
            arrays = [indices_retain[1:], indices_split1, indices_split2]

            # 记录每个序列已考虑过的下标
            indices = [0 for _ in range(len(arrays))]
            while not is_finish(arrays, indices):
                min_value_idx = None
                idx_to_increase = -1
                for i in range(0, len(arrays)):
                    # 序列arrays[i]已结束，不考虑
                    if indices[i] >= len(arrays[i]):
                        continue
                    idx = arrays[i][indices[i]]
                    # 序列arrays[i]未结束，查看是否为最小值
                    if min_value_idx is None or cosine((q[idx][0] - origin[0], q[idx][1] - origin[1])) > cosine((q[min_value_idx][0] - origin[0], q[min_value_idx][1] - origin[1])):
                        min_value_idx = idx
                        idx_to_increase = i
                indices[idx_to_increase] += 1
                result.append(min_value_idx)
            return result

        # 只有1个顶点，直接返回
        if len(indices) == 1:
            return indices

        # 有2个顶点，按y值小的在前顺序返回
        if len(indices) == 2:
            if q[indices[0]][1] < q[indices[1]][1]:
                return indices
            else:
                return [indices[1], indices[0]]

        # 有3个顶点，取y值最小的作为原点，按极角递增顺序排序
        if len(indices) == 3:
            q0_idx = indices[0]
            for i in indices[1:]:
                if q[i][1] < q[q0_idx][1]:
                    q0_idx = i
            q0 = q[q0_idx]
            return [q0_idx] + sorted([i for i in indices if i != q0_idx], key=lambda i: -cosine((q[i][0] - q0[0], q[i][1] - q0[1])))

        # 有4个及以上顶点，分治
        # 求x的平均值
        avg_x = 0
        for i in indices:
            avg_x += q[i][0]
        avg_x /= len(indices)

        # 以x的平均值划分顶点
        indices_left = []
        indices_right = []
        for i in indices:
            if q[i][0] < avg_x:
                indices_left.append(i)
            else:
                indices_right.append(i)

        # 分治，左右返回的顶点均是y值最小的在前，且按极角排序
        indices_left = divide_and_conquer_inner(q, indices_left)
        indices_right = divide_and_conquer_inner(q, indices_right)

        # 找到新的y最小的点作为原点
        q0_idx_left = indices_left[0]
        q0_idx_right = indices_right[0]
        if q[q0_idx_left][1] < q[q0_idx_right][1]:
            q0_idx = q0_idx_left
            indices_retain = indices_left
            indices_split = indices_right
        else:
            q0_idx = q0_idx_right
            indices_retain = indices_right
            indices_split = indices_left
        q0 = q[q0_idx]

        # 将不包含新原点的一边划分为顺时针和逆时针两部分
        smallest_idx = 0
        biggest_idx = 0
        for i in range(1, len(indices_split)):
            if cosine((q[indices_split[i]][0] - q0[0], q[indices_split[i]][1] - q0[1])) > cosine((q[indices_split[smallest_idx]][0] - q0[0], q[indices_split[smallest_idx]][1] - q0[1])):
                smallest_idx = i
            if cosine((q[indices_split[biggest_idx]][0] - q0[0], q[indices_split[biggest_idx]][1] - q0[1])) > cosine((q[indices_split[i]][0] - q0[0], q[indices_split[i]][1] - q0[1])):
                biggest_idx = i
        if smallest_idx < biggest_idx:
            indices_split1 = indices_split[smallest_idx : biggest_idx + 1]
            indices_split2 = indices_split[biggest_idx + 1:] + indices_split[:smallest_idx]
        else:
            indices_split1 = indices_split[smallest_idx:] + indices_split[:biggest_idx + 1]
            indices_split2 = indices_split[biggest_idx + 1 : smallest_idx]
        indices_split2.reverse()

        # 归并
        indices = merge(q, indices_retain, indices_split1, indices_split2)

        # 对归并后的顶点运行granham scan
        indices = graham_scan_inner(q, indices)
        return indices

    return divide_and_conquer_inner(q, [i for i in range(len(q))])


def wrapper(algo, input):
    start_time = datetime.now()
    result = algo(input)
    end_time = datetime.now()
    return result, end_time - start_time


def test_case(algorithm, input_size):
    q = [(random.random() * 100, random.random() * 100) for _ in range(input_size)]
    return wrapper(algorithm, q)


if __name__ == '__main__':
    parser = ArgumentParser()
    parser.add_argument('--random_seed', type=int, default=19950125)
    parser.add_argument('--input_size', type=int, default=1000)
    parser.add_argument('--algorithm', type=str, default='enum')
    parser.add_argument('--input_file', type=str, default='')
    option = parser.parse_args()

    random.seed(option.random_seed)

    algorithm = {
        'enum': enum,
        'graham': graham_scan,
        'dnc': divide_and_conquer
    }[option.algorithm]

    if option.input_file.strip() == '':
        print('算法：%s，输入大小：%d' % (option.algorithm, option.input_size))
        result, timedelta = test_case(algorithm, option.input_size)
        print('用时：' + format_timedelta(timedelta))
    else:
        q = []
        with open(option.input_file, 'r') as f:
            for line in f:
                x, y = line.strip().split()
                q.append((float(x), float(y)))
        result, timedelta = wrapper(algorithm, q)
        result_print = [i + 1 for i in result]
        print('输出：' + str(result_print))
        print('用时：' + format_timedelta(timedelta))
        with open('convex_hull.js', 'w') as f:
            f.write('var POINTS = [\n')
            for p in q:
                f.write('    [' + str(p[0]) + ', ' + str(p[1]) + '],\n')
            f.write('];\n')
            f.write('var CONVEX_HULL = [\n')
            f.write('    ' + ', '.join(str(i) for i in result) + '\n')
            f.write('];\n')
